import java.util.Arrays;

public class SolutionInterview17_24 {
    public int[] getMaxMatrix(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int[][] sum=new int[m+1][n+1];
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                sum[i][j]=sum[i-1][j]+sum[i][j-1]+matrix[i-1][j-1]-sum[i-1][j-1];
            }
        }
        int max=Integer.MIN_VALUE,xS=-1,yS=-1,xE=-1,yE=-1;
        for (int i=0;i<matrix.length;i++){
            for (int j=i;j<matrix.length;j++){
                int[] f=new int[matrix[0].length];
                for (int k=0;k<f.length;k++){
                    f[k]=cal(sum,i,k,j,k);
                }
                int[] g=new int[f.length];
                int[] h=new int[f.length];
                g[0]=f[0];
                h[0]=0;
                if (g[0]>max){
                    max=g[0];
                    xS=i;
                    yS=h[0];
                    xE=j;
                    yE=0;
                }
                for (int k=1;k<f.length;k++){
                    if (g[k-1]<0){
                        g[k]=f[k];
                        h[k]=k;
                    }else {
                        g[k]=f[k]+g[k-1];
                        h[k]=h[k-1];
                    }
                    if (g[k]>max){
                        max=g[k];
                        xS=i;
                        yS=h[k];
                        xE=j;
                        yE=k;
                    }
                }
            }
        }
        return new int[]{xS,yS,xE,yE};
    }

    private int cal(int[][] sum, int a, int b, int c, int d) {
        return sum[c+1][d+1]-sum[a][d+1]-sum[c+1][b]+sum[a][b];
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionInterview17_24().getMaxMatrix(new int[][]{{-4, -5}})));
    }
}
